Educational Codeforces Round 47 Div2

打的好cha，最近疯狂吃shit

---

E. Intercity Travelling

题意

x轴正向有长度n的公路，$1$ ~ $n-1$每个点都有可能有加油站(显然共有 $2^{n-1}$种可能)，每次到了一个加油站就要从1开始从新，每个距离的贡献为$a_i(1<=i<=n)$,问总贡献的期望值 × $2^{n-1}$ % 998244353

题解

考虑 $2^{n-1}$ 种情况，每个$a_i$的贡献次数都是确定的，故算出每个数的贡献即可，但是每个$a_i$出现的次数怎么算？
这个没想到怎么算？
反过来，我们考虑每个位置对于每个$a_i$出现的概率，因为每个位置是否安置加油站的概率都是1/2，故可以递推出每个位置可能的$a_i$的概率，再× $2^{n-1}$即可

推导过程：

...
...
a4                  1/8  1/16  1/16
a3            1/4   1/8  1/8   1/8
a2      1/2   1/4   1/4  1/4   1/4
a1  1   1/2   1/2   1/2  1/2   1/2
    1   2     3     4    5     6